/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
// 解题思路采用二分查找，就需要排序
int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

int binSearch(int *nums, int numsSize, int start, int k)
{
    int low = start;
    int high = numsSize - 1;
    int mid;
    while (low <= high)
    {
        mid = (high + low) / 2;
        if (nums[mid] > k)
        {
            high = mid - 1;
        }
        else if (nums[mid] < k)
        {
            low = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    /* 搜索不到值则返回-1 */
    return -1;
}

// 计算全排列
int ComputeMax(int Size)
{
    int i;
    int m = 1;
    int n = 1;
    for (i = 1; i <= Size; i++)
    {
        n *= i;
        if (i <= (Size - 3))
        {
            m *= i;
        }
    }
    return n / (m * 6);
}
int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes)
{
    int i;
    int j;
    int tmp;
    int idx;
    int maxSize;
    (*returnSize) = 0;
    if (numsSize < 3)
    {
        return NULL;
    }

    int **ret = (int **)malloc(sizeof(int *) * numsSize * numsSize);
    *returnColumnSizes = (int *)malloc(sizeof(int) * numsSize * numsSize);
    // 先升序排序
    qsort(nums, numsSize, sizeof(int), &compare);
    for (i = 0; i < numsSize - 2; i++)
    {
        for (j = i + 1; j < numsSize - 1; j++)
        {
            tmp = -(nums[i] + nums[j]);
            idx = binSearch(nums, numsSize, j + 1, tmp);
            if (idx != -1)
            {
                ret[(*returnSize)] = (int *)malloc(sizeof(int) * 3);
                ret[(*returnSize)][0] = nums[i];
                ret[(*returnSize)][1] = nums[j];
                ret[(*returnSize)][2] = tmp;
                (*returnColumnSizes)[*returnSize] = 3;
                (*returnSize)++;
            }
        }
    }
    // 结果定义排序，再去重

    return ret;
}